In general, a state machine may be any device that stores a particular status at a particular time. A state machine may change state (i.e., change status) based on an input and/or cause an action or output to take place based on a change in state. States are typically connected by “transitions” wherein each transition is labeled with the name of an input event. When that event occurs, the corresponding transition is followed from the current state to arrive at the new state.
FIG. 1 is a diagram showing transitions between states of a simple state machine. In this example, the state machine can be in one of five states: states s(0), s(1), s(2), s(3), and s(4). Each state causes its own set of outputs to be asserted. The outputs could be any number of signals. The state machine stays in a state until an appropriate input event condition is satisfied. For instance, if the state machine is in state s(0), it stays in that state with output signal(s) o(0) asserted until input event i(1a) occurs, which causes the state machine to make a transition to the state s(1), or input event i(1b) occurs, which causes a transition to state s(2).
A state machine is useful whenever it is necessary to implement a program having input events with multiple states depending on those events. These situations arise frequently in communications, parsing, emulations, and handling user inputs to name a few. A computer may be considered a state machine wherein each instruction or request that is input to the computer may change one or more states, thereby causing other actions to take place.
State machines often do not work properly for a variety of reasons. The state machine may fall into two conflicting valid states which are caused by mistakes or oversights of the system designer. In such a case, the state machine may malfunction or may cause other state machines to malfunction. Since the problem can cascade from one state machine to other state machines, it is difficult to determine which state machine caused the problem without a proper tracking mechanism. Therefore, it would be desirable to provide a function for tracing the states of state machines.